package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-13 0:10
 */
public class DifferentWay2 {
    public static void main(String[] args) {

    }

    /**leetcode 63
     1.我们初始化为一个二维数组，数组的下标代表当前走到的位置，数组的大小代表当前走到这个位置的方法数2.递推公式，考虑到
     * 走到每一个格子之前只能由这个格子的左边和格子的上边推出来，所以递推公式应该这样理解：dp[i][j]=dp[i][j-1]+dp[i-1][j]（但是要考虑条件限制）
     * 3.初始化数组：由于每个元素都是有其上面的元素和左边的元素相加而来，所以需要初始化最上面和最左边的一行和一列元素
     * 4.遍历顺序，由上和左推出元素，所以遍历方式自然是从左往右和从上往下
     * @return
     */
    public static  int differentWay(int[][]hinder,int rol,int col){
        //排除特殊情况
        if(hinder[0][1]==1||hinder[rol][col]==1){
            //初始值和最后的值为1时，直接返回0
            return 0;
        }
        //创建数组
        int[][]dp=new int[rol+1][col+1];
        //初始化数组
        for(int i=0;i<dp.length;++i){
            if(hinder[i][0]==0){
                dp[i][0]=1;
            }else{
                break;
            }
        }
        for(int i=0;i<dp[0].length;++i){
            if(hinder[0][i]==0){
                dp[0][i]=1;
            }else{
                break;
            }
        }
        //遍历数组，对于有障碍的数组，使其值为0
        for(int i=1;i< dp.length;++i){
            for (int j = 1; j <dp[0].length ; j++) {
                if(hinder[i][j]==0){
                    dp[i][j]=dp[i][j-1]+dp[i-1][j];
                }
            }
        }
        //最后返回值
        return dp[rol][col];

    }
}
